Konsep 'Melayu Raya' atau 'Nusantara' telah wujud pada zaman Srivijaya dan Majapahit lagi. Kerajaan Srivijaya yang terletak di Palembang, Sumatera telah menguasai sebahagian Tanah Melayu. Kerajaan Majapahit yang terletak di Pulau Jawa juga pernah menguasai wilayah yang sama. Kesultanan Melayu Melaka dari 1402 hingga 1511 juga pernah menguasai Tanah Melayu dan menjangkau ke pantai timur Sumatera.

Sejarah Indonesia dan Sejarah Malaysia sering terjalin. Sepanjang sejarah mereka, sempadan kerajaan dan empayar purba - seperti Srivijaya, Majapahit, Melaka, Johor-Riau dan Brunei - sering merangkumi kedua-dua negara moden. Selama berabad-abad, hubungan, penghijrahan, dan interaksi antara rakyat Indonesia dan Malaysia agak sengit, dan adalah perkara biasa bagi rakyat Malaysia untuk mengesan saudara mereka di Indonesia dan sebaliknya. Rumah orang Melayu berada di kedua-dua belah selat dan juga di pantai Borneo, manakala tanah air Dayak kedua-duanya di Borneo Malaysia Timur dan Kalimantan, Indonesia.[8]

Penghijrahan orang Indonesia ke Malaysia dapat dikesan sejak sebelum zaman penjajahan terutama pada zaman pemerintahan Srivijaya dan Majapahit. Raja pertama Kesultanan Melaka adalah keturunan langsung putera Srivijaya dari Palembang. Perkahwinan antara Kerajaan seperti Sultan Mansur Syah Malaka dengan Puteri Raden Galuh Chandra Kirana dari Majapahit disebut dalam Sejarah Melayu. Teks sejarah lain seperti Tuhfat al-Nafis (dikenali sebagai Sejarah Melayu dan Bugis), menyatakan hubungan yang dekat antara Kesultanan Johor-Riau, Kedah, Perak, Selangor, Pahang, dan Terengganu di semenanjung dengan kerajaan kerajaan di kepulauan Indonesia.[9]

Semasa era penjajahan, wilayah ini telah dipertandingkan di kalangan kuasa penjajah Eropah, terutamanya British dan Belanda. Dari abad ke-17 hingga awal abad ke-19, pelbagai negeri, pelabuhan, dan bandar di rantau ini telah dipegang sebagai tanah jajahan Belanda atau milik British. Sempadan semasa antara Indonesia dan Malaysia diwarisi daripada yang ditubuhkan oleh kuasa penjajah melalui perjanjian mereka. Perjanjian Inggeris-Belanda 1814 dan 1824 secara signifikan membentuk wilayah Indonesia san Malaysia.[10]

Apabila British mengambil alih kuasa ke atas seluruh wilayah Malaysia masa kini pada zaman penjajahan, Malaysia telah diintegrasikan ke dalam pasaran komoditi dan modal dunia, menjadi penyedia sumber untuk penjajahnya (suzerain) dan mula menghadapi kekurangan pekerja buruh. British kemudiannya mencari sumber buruh dari negara seperti India dan China. Orang Indonesia menjadi sumber buruh ketiga dan British memandang serta melayan mereka berbeza daripada orang India dan Cina kerana mereka dianggap berasal daripada kaum yang sama dengan orang Melayu. Corak layanan berbeza untuk migran berdasarkan etnik telah diwujudkan, yang mempunyai implikasi besar untuk penghijrahan buruh ke Tanah Melayu selepas kemerdekaan pada tahun 1957.[11]

Selepas dekolonisasi, kerajaan, seperti institusi politik lain dalam demokrasi, cuba mengekalkan mandat dan legitimasinya melalui pilihan raya. Ini mempunyai implikasi untuk menyediakan insentif dan meluaskan asas sokongan. Dengan mengklasifikasikan pendatang Indonesia (seperti Jawa, Minangkabau, Bugis, Bawean, Banjar, Mandailing, Aceh dan lain-lain) kepada etnik Melayu, parti kerajaan Pertubuhan Kebangsaan Melayu Bersatu atau UMNO meluaskan pangkalan massanya. Sebab klasifikasi dan kriteria etnik Melayu dalam perlembagaan Malaysia adalah pembinaan sosio-sejarah. Aspek sejarah ini wujud kerana identiti yang ditakrifkan dalam perlembagaan Malaysia telah wujud sejak zaman kesultanan Melaka berbeza dengan Orang Asli atau orang Dayak. Sehingga sesiapa yang memenuhi kehendak sosio-agama orang Melayu digolongkan sebagai Melayu.